package com.jia.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 131.分割回文串
 * 
 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author Administrator
 *
 */
public class Pro0131 {
    List<List<String>> ans;
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        if(s == null || s.length() == 0) return ans;
        this.ans = ans;
        bracktracking(s, 0,new ArrayList<String>());
        return ans;
    }

    /**
     *
     * @param s  字符串
     * @param index  字符串开始下表
     * @param list    存储当前都是回文串的集合
     */
    private void bracktracking(String s, int index, List<String> list ){
        //1.终止条件
        if(index == s.length()) {
            //需要copy一分
            ans.add(new ArrayList<String>(list));
        }
        for(int i = index; i < s.length(); i++) {
            if(!isPlalindrome(s, index, i)) { //进行剪枝
                continue;
            }
            //2.选择
            list.add(s.substring(index, i + 1));
            //3.drill down 下一层
            bracktracking(s, i+1, list);
            //4.撤销
            list.remove(list.size() - 1);
        }
    }
    //判断字符串str，对应下表[st..ed]是否为回文字符串
    private boolean isPlalindrome(String str, int st, int ed) {
        if(st > ed) return false;
        while(st <= ed) {
            if(str.charAt(st) != str.charAt(ed)) {
                return false;
            }
            ++st;
            --ed;
        }
        return true;
    }

}
